package com.mlh.dp.knapsackProblem;

//组合总和4
//给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
// 题目数据保证答案符合 32 位整数范围。

// 输入：nums = [1,2,3], target = 4
// 输出：7
// 解释：
// 所有可能的组合为：
// (1, 1, 1, 1)
// (1, 1, 2)
// (1, 2, 1)
// (1, 3)
// (2, 1, 1)
// (2, 2)
// (3, 1)
// 请注意，顺序不同的序列被视作不同的组合

//背包问题转化  target就是背包容量  nums数组则是物品数组
//问题就是装满宝贝有多少张方式
public class CombinationSum4 {

    public static void main(String[] args) {
        int[]nums={1,2,3};
        method2(nums,4);
    }

    public int method1(int[] nums, int target) {
        return process1(nums,target);
    }

    public int process1(int[] nums, int target) {
        if(target<=0){
            return target==0?1:0;
        }
        int res=0;
        for(int i=0;i<nums.length;i++){
            res+=process1(nums,target-nums[i]);
        }
        return res;
    }

    public static int method2(int[] nums, int target) {
        int[]dp=new int[target+1];
        //这里dp[0]=1非常重要，i-nums[j]=0  此时肯定算一种方法了
        //这也是起始条件
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for (int j=0;j<nums.length;j++){
                if(i-nums[j]>=0){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}
